module Arbol23 where

data Arbol23 a b = Hoja a | Dos b (Arbol23 a b) (Arbol23 a b) | Tres b b (Arbol23 a b) (Arbol23 a b) (Arbol23 a b)

{- Funciones para mostrar el árbol. -}

instance (Show a, Show b) => Show (Arbol23 a b) where
    show x = concatMap (++"\n") (padTree 0 x)

padTree:: (Show a, Show b) => Int -> (Arbol23 a b)-> [String]
padTree i (Hoja x) = [(pad i) ++  (show x)]
padTree i (Dos x a1 a2) = [(pad i) ++  (show x) ] ++ (concatMap (padTree (i + 4)) [a1,a2])
padTree i (Tres x y a1 a2 a3) = [(pad i) ++  (show x) ++ (' ':(show y))] ++ (concatMap (padTree (i + 4)) [a1,a2,a3])

pad:: Int -> String
pad i = replicate i ' '

{- Funciones pedidas. -}
-- Ejercicio 1
foldA23 :: (a -> d ) -> (b -> d -> d -> d ) -> (b -> b -> d -> d -> d -> d) -> (Arbol23 a b)  -> d
foldA23 fHoja _ _ (Hoja x)              = fHoja x
foldA23 fHoja fDos fTres (Dos x izq der)   = fDos x (foldA23 fHoja fDos fTres izq) (foldA23 fHoja fDos fTres der)
foldA23 fHoja fDos fTres (Tres x y izq med der)   = fTres x y 
                                                    (foldA23 fHoja fDos fTres izq) 
                                                    (foldA23 fHoja fDos fTres med)
                                                    (foldA23 fHoja fDos fTres der)

--Ejercicio 2.a
--Lista las hojas de izquierda a derecha.
hojas::Arbol23 a b->[a] 
hojas = foldA23(\n -> [n])(\x rec_izq rec_der -> rec_izq ++ rec_der)(\x y rec_izq rec_med rec_der -> rec_izq ++ rec_med ++ rec_der)

--Ejercicio 2.b
--Lista en preorden de los internos del árbol.
internos::Arbol23 a b -> [b]
internos = foldA23 (\n -> [])(\x rec_izq rec_der -> [x] ++ rec_izq ++ rec_der)(\x y rec_izq rec_med rec_der -> [x,y] ++ rec_izq ++ rec_med ++ rec_der)


--Ejercicio 2.c
--No podemos usar pattern matching aca? APara q usar fold?
esHoja::Arbol23 a b->Bool
esHoja = foldA23(\_ -> True)(\_ _ _ -> False)(\_ _ _ _ _ -> False)

--Ejercicio 3
mapA23::(a->c)->(b->d)->Arbol23 a b->Arbol23 c d
mapA23 fHoja fNodo = 	foldA23(\x -> Hoja (fHoja x))
						(\x rec_izq rec_der -> Dos (fNodo x) rec_izq rec_der)
						(\x y rec_izq rec_med rec_der -> Tres (fNodo x) (fNodo y) rec_izq rec_med rec_der)


--Ejercicio 4
--Trunca el árbol hasta un determinado nivel. Cuando llega a 0, reemplaza el resto del árbol por una hoja con el valor indicado.
--Funciona para árboles infinitos.
truncar::a->Integer->Arbol23 a b->Arbol23 a b
truncar a n arbol= (foldNat truncarAux (truncarBase a)) n arbol

foldNat :: (b -> b) -> b -> Integer -> b
foldNat s z 0 = z
foldNat s z n = s (foldNat s z (n-1))

truncarBase::a->Arbol23 a b->Arbol23 a b
truncarBase a _ = Hoja a
  
truncarAux::(Arbol23 a b->Arbol23 a b)->Arbol23 a b->Arbol23 a b
truncarAux f (Hoja x)= (Hoja x)
truncarAux f (Dos x izq der)= Dos x (f izq) (f der)
truncarAux f (Tres x y izq med der)= Tres x y (f izq) (f med) (f der)

--Ejercicio 5
--Evalúa las funciones tomando los valores de los hijos como argumentos.
--En el caso de que haya 3 hijos, asocia a izquierda.
evaluar::Arbol23 a (a->a->a)->a
evaluar arbol= foldA23 id evalDos evalTres arbol

--Definicion para usar con el foldA23 para arboles construidos con el constructor Dos
evalDos::(a->a->a)->a->a->a
evalDos x izq der= x izq der 

--Definicion para usar con el foldA23 para arboles construidos con el constructor Tres
evalTres::(a->a->a)->(a->a->a)->a->a->a->a
evalTres x y izq med der= y (x izq med) der


{- Arboles de ejemplo. -}
arbolito1::Arbol23 Char Int
arbolito1 = Tres 0 1
	      (Dos 2 (Hoja 'a') (Hoja 'b'))
	      (Tres 3 4 (Hoja 'c') (Hoja 'd') (Dos 5 (Hoja 'e') (Hoja 'f')))
	      (Dos 6 (Hoja 'g') (Dos 7 (Hoja 'h') (Hoja 'i')))

arbolito2::Arbol23 Int Bool
arbolito2 = Dos True (Hoja (-1)) (Tres False True (Hoja 0) (Hoja (-2)) (Hoja 4))

arbolito3::Arbol23 Int (Int->Int->Int)
arbolito3 = Dos (+) (Tres (*) (-) (Hoja 1) (Hoja 2) (Hoja 3)) (incrementarHojas arbolito3)

--Ejemplos:
--Ejemplo de uso de mapA23.
--Incrementa en 1 el valor de las hojas.
incrementarHojas::Num a =>Arbol23 a b->Arbol23 a b
incrementarHojas = mapA23 (+1) id
--internos arbolito1 = [0,1,2,3,4,5,6,7]
--hojas arbolito1 = "abcdefghi"
--hojas (incrementarHojas arbolito2) = [0,1,-1,5]
--internos arbolito2 = [True,False,True]
--take 10 (hojas arbolito3) = [1,2,3,2,3,4,3,4,5,4]
--hojas (truncar 0 6 arbolito3) = [1,2,3,2,3,4,3,4,5,4,5,6,0,0,0,0,0]
--evaluar (truncar 0 6 arbolito3) = 22 = (1*2-3)+(2*3-4)+(3*4-5)+(4*5-6)
